"""
https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels
"""


from typing import List


class Solution:

    # 暴力 O(m*n)
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        l, r, u, d = y, y, x, x
        for i in range(m):
            for j in range(n):
                if image[i][j] == "1":
                    l = min(l, j)
                    r = max(r, j)
                    u = min(u, i)
                    d = max(d, i)
        return (d - u + 1) * (r - l + 1)

    # dfs, bfs  O(n_black) 最坏情况还是 O(m * n)
    def minArea():
        pass

    # 二分。投影的概念。
    # 二分枚举 上：然后如果一行都为0则取下，否则收集答案继续向上。      O(logm * n)
    #   同理枚举下，左，右
    # 时间复杂度O(m*logn + n*logm)
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        def f(l, r, is_go_up):
            ans = -1
            while l <= r:
                mid = l + r >> 1
                res = False
                for j in range(n):
                    if image[mid][j] == "1":
                        res = True
                        break
                if res:
                    ans = mid
                    if is_go_up:
                        r = mid - 1
                    else:
                        l = mid + 1
                else:
                    if is_go_up:
                        l = mid + 1
                    else:
                        r = mid - 1
            return ans

        def g(l, r, is_go_left):
            ans = -1
            while l <= r:
                mid = l + r >> 1
                res = False
                for i in range(m):
                    if image[i][mid] == "1":
                        res = True
                        break
                if res:
                    ans = mid
                    if is_go_left:
                        r = mid - 1
                    else:
                        l = mid + 1
                else:
                    if is_go_left:
                        l = mid + 1
                    else:
                        r = mid - 1
            return ans

        up = f(0, x, True)
        print(up)
        down = f(x, m-1, False)
        print(down)
        left = g(0, y, True)
        print(left)
        right = g(y, n - 1, False)
        print(right)
        return (down - up + 1) * (right - left + 1)

image = [["0", "0", "1", "0"], ["0", "1", "1", "0"], ["0", "1", "0", "0"]]
print(Solution().minArea(image, 0, 2))
